package greedy.leetcode_253;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MinHeapSolution {
    public int minMeetingRooms(int[][] intervals) {
        // 按会议的开始时间升序排列
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        /*
            利用最小堆，按会议的结束时间存放，如果当前会议的开始时间 > 堆顶会议的结束时间，说明存在空闲会议室
        */
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < intervals.length; i++) {
            if (!minHeap.isEmpty() && intervals[i][0] >= minHeap.peek()) {
                minHeap.poll();
            }
            minHeap.offer(intervals[i][1]);
        }
        // 堆的容量就是所需要的会议室数量
        return minHeap.size();
    }
}
